// https://www.lintcode.com/problem/course-schedule-iii/description

bool cmp(vector<int> course1, vector<int> course2)
{
    return course1[1] < course2[1];
}
class Solution {
public:
    /**
     * @param courses: duration and close day of each course
     * @return: the maximal number of courses that can be taken
     */
    // 贪心，按截止日期排序，选持续时间尽量短的。能放的往里放，不能放的替换里面的时间最长的。
    int scheduleCourse(vector<vector<int>> &courses) {
        sort(courses.begin(), courses.end(), cmp);
        priority_queue<int> q;
        int time = 0; //第一天也学
        for (int i = 0; i < courses.size(); ++i)
        {
            if (time + courses[i][0] <= courses[i][1])
            {
                time += courses[i][0];
                q.push(courses[i][0]);
            }
            else if (!q.empty() && q.top() > courses[i][0])
            {
                time += courses[i][0] - q.top();
                q.pop();
                q.push(courses[i][0]);
            }
        }
        return q.size();
    }
};